package problems.contest;

import java.util.*;

/**
 * @author dubulingbo, 2023/6/14 20:24.
 */
public class WCT305 {

    /**
     * T2|6139.受限条件下可到达节点的数目
     * <p></p>
     */
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<Integer>[] ed = new List[n];

        for (int[] e : edges) {
            if (ed[e[0]] == null) {
                List<Integer> arr = new ArrayList<>();
                arr.add(e[1]);
                ed[e[0]] = arr;
            } else {
                ed[e[0]].add(e[1]);
            }
            if (ed[e[1]] == null) {
                List<Integer> list = new ArrayList<>();
                list.add(e[0]);
                ed[e[1]] = list;
            } else {
                ed[e[1]].add(e[0]);
            }
        }

        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> que = new LinkedList<>();
        HashSet<Integer> re = new HashSet<Integer>();

        for (int r : restricted) {
            re.add(r);
        }


        que.offer(0);
        visited.add(0);
        int st;
        while (!que.isEmpty()) {
            st = que.poll();

            if (ed[st] != null) {
                for (int en : ed[st]) {
                    if (!visited.contains(en) && !re.contains(en)) {
                        que.offer(en);
                        visited.add(en);
                    }
                }
            }
        }

        return visited.size();
    }


    /**
     * T3|6137.检查数组是否存在有效划分
     * <p></p>
     */
    public boolean validPartition(int[] nums) {
        int n = nums.length;

        // [i][0] 表示划分成2个
        // [i][1] 表示划分成3个
        boolean[][] dp = new boolean[n][2];

        dp[1][0] = nums[0] == nums[1];

        for (int i = 1; i < n; ++i) {
            if (i - 2 >= 0) {
                dp[i][0] = (nums[i] == nums[i-1]) && (dp[i-2][0] || dp[i-2][1]);
            }

            if (i >= 3) {
                dp[i][1] = f(nums[i-2], nums[i-1], nums[i]) && (dp[i-3][0] || dp[i-3][1]);
            } else if (i >= 2) {
                dp[i][1] = f(nums[i-2], nums[i-1], nums[i]);
            }

//            if (!dp[i][0] && !dp[i][1]) return false;
        }

        return dp[n-1][0] || dp[n-1][1];

    }

    private boolean f(int a, int b, int c) {
        if (a == b && b == c) return true;
        if (b - a == 1 && c - b == 1) return true;
        return false;
    }


    /**
     * T4|6138.最长理想子序列
     * <p></p>
     */
    public int longestIdealString(String s, int k) {
        char[] chs = s.toCharArray();
        int[] maxMap = new int[26];
        int ans = 0;

        for (char ch : chs) {
            int max = 1;
            for (char c = (char) (ch - k); c <= ch + k; ++c) {
                if (c >= 'a' && c <= 'z') {
                    max = Math.max(maxMap[c - 'a'], max);
                }
            }
            maxMap[ch - 'a'] = max;
            ans = Math.max(max, ans);
        }

        return ans;
    }
}
